import java.security.KeyPair;
import java.sql.Array;
import java.util.*;


class Node {
    public int val;
    public List<Node> children;
    public Node() {}
    public Node(int _val) {
        val = _val;
    }
    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
};

class TreeNode {
   int val;
   TreeNode left;
   TreeNode right;
   TreeNode() {}
   TreeNode(int val) { this.val = val; }
   TreeNode(int val, TreeNode left, TreeNode right) {
       this.val = val;
       this.left = left;
       this.right = right;
   }
}
public class Test {


    //在每个树行中找最大值
    public List<Integer> largestValues(TreeNode root) {
        List<Integer> ret = new ArrayList<>();

        if (root == null) return ret;

        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);

        while (!q.isEmpty()) {
            int sz = q.size();
            int tmp = Integer.MIN_VALUE;
            for (int i = 0; i < sz; i++) {
                TreeNode t = q.poll();
                tmp = Math.max(tmp, t.val);
                if (t.left != null) q.add(t.left);
                if (t.right != null) q.add(t.right);
            }
            ret.add(tmp);
        }
        return ret;
    }



    //二叉树的最大宽度
    public int widthOfBinaryTree(TreeNode root){
        List<Pair<TreeNode,Integer>> q = new ArrayList<>();
        q.add(new Pair<TreeNode,Integer>(root,1));
        int ret = 0;

        while(!q.isEmpty()){
            // 先更新⼀下这⼀层的宽度
            Pair<TreeNode, Integer> t1 = q.get(0);
            Pair<TreeNode, Integer> t2 = q.get(q.size() - 1);
            ret = Math.max(ret, t2.getValue() - t1.getValue() + 1);
            // 让下⼀层进队
            List<Pair<TreeNode, Integer>> tmp = new ArrayList<>();
            for(Pair<TreeNode, Integer> t : q)
            {
                TreeNode node = t.getKey();
                int index = t.getValue();
                if(node.left != null)
                {
                    tmp.add(new Pair<TreeNode, Integer>(node.left, index * 2));
                }
                if(node.right != null)
                {
                    tmp.add(new Pair<TreeNode, Integer>(node.right, index * 2 + 1));
                }
            }
            q = tmp;
        }
        return ret;
    }
    }




    //二叉树的锯齿形层序遍历
    public List<List<Integer>> zigzagLevelOrder(TreeNode root){
        List<List<Integer>> ret = new ArrayList<>();
        if (root == null) return ret;
        Queue<TreeNode> q = new LinkedList<>();

        q.add(root);
        int level = 1;

        while(!q.isEmpty()){
            int sz = q.size();
            List<Integer> tmp = new ArrayList<>();
            for (int i = 0; i < sz; i++) {
                TreeNode t = q.poll();
                tmp.add(t.val);
                if (t.left != null) q.add(t.left);
                if (t.right != null) q.add(t.right);
            }

            //判断是否逆序
            if (level % 2 == 0) Collections.reverse(tmp);
            ret.add(tmp);
            level++;
        }
        return ret;
    }




    //N叉树的层序遍历
    public List<List<Integer>> levelOrder(Node root){
        List<List<Integer>> ret = new ArrayList<>();
        if (root == null) return ret;
        Queue<Node> q = new LinkedList<>();
        q.add(root);

        while (!q.isEmpty()){
            int sz = q.size();
            List<Integer> tmp = new ArrayList<>();

            for (int i = 0; i < sz; i++) {
                Node t  =q.poll();
                tmp.add(t.val);
                for (Node child: t.children) {
                    if (child!= null){
                        q.add(child);
                    }
                }
            }
            ret.add(tmp);
        }
        return ret;
    }

}
